{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #交通枢纽"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: transportationHub"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #交通枢纽"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "为了缓解「力扣嘉年华」期间的人流压力，组委会在活动期间开设了一些交通专线。`path[i] = [a, b]` 表示有一条从地点 `a`通往地点 `b` 的 **单向** 交通专线。\n",
    "若存在一个地点，满足以下要求，我们则称之为 **交通枢纽**：\n",
    "- 所有地点（除自身外）均有一条 **单向** 专线 **直接** 通往该地点；\n",
    "- 该地点不存在任何 **通往其他地点** 的单向专线。\n",
    "\n",
    "请返回交通专线的 **交通枢纽**。若不存在，则返回 `-1`。\n",
    "\n",
    "**注意：**\n",
    "- 对于任意一个地点，至少被一条专线连通。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`path = [[0,1],[0,3],[1,3],[2,0],[2,3]]`\n",
    ">\n",
    ">输出：`3`\n",
    ">\n",
    ">解释：如下图所示：\n",
    "> 地点 `0,1,2` 各有一条通往地点 `3` 的交通专线，\n",
    "> 且地点 `3` 不存在任何**通往其他地点**的交通专线。\n",
    ">![image.png](https://pic.leetcode-cn.com/1663902572-yOlUCr-image.png){:width=200px}\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`path = [[0,3],[1,0],[1,3],[2,0],[3,0],[3,2]]`\n",
    ">\n",
    ">输出：`-1`\n",
    ">\n",
    ">解释：如下图所示：不存在满足 **交通枢纽** 的地点。\n",
    ">![image.png](https://pic.leetcode-cn.com/1663902595-McsEkY-image.png){:width=200px}\n",
    "\n",
    "**提示：**\n",
    "- `1 <= path.length <= 1000`\n",
    "- `0 <= path[i][0], path[i][1] <= 1000`\n",
    "- `path[i][0]` 与 `path[i][1]` 不相等"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [D9PW8w](https://leetcode.cn/problems/D9PW8w/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [D9PW8w](https://leetcode.cn/problems/D9PW8w/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[0,3],[1,3],[2,0],[2,3]]', '[[0,3],[1,0],[1,3],[2,0],[3,0],[3,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        in_degrees = defaultdict(int)\n",
    "        out_degrees = defaultdict(int)\n",
    "        node_set = set()\n",
    "        for p in path:\n",
    "            out_degrees[p[0]] += 1\n",
    "            in_degrees[p[1]] += 1\n",
    "            node_set.add(p[0])\n",
    "            node_set.add(p[1])\n",
    "        for node, in_degree in in_degrees.items():\n",
    "            if in_degree == len(node_set) - 1 and node not in out_degrees:\n",
    "                return node\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        deg = [0] * 1001\n",
    "        ind = [0] * 1001\n",
    "        v = set()\n",
    "        for a, b in path:\n",
    "            deg[a] += 1\n",
    "            ind[b] += 1\n",
    "            v.add(a)\n",
    "            v.add(b)\n",
    "        n = len(v)\n",
    "        for i in range(n):\n",
    "            if ind[i] == n - 1 and deg[i] == 0:\n",
    "                return i \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        col = [0] * 1001\n",
    "        row = [0] * 1001\n",
    "        m = 0\n",
    "        for p in path:\n",
    "            m = max(p[0], p[1], m)\n",
    "            col[p[1]] += 1\n",
    "            row[p[0]] += 1\n",
    "        for i in range(m + 1):\n",
    "            if col[i] == m and row[i] == 0:\n",
    "                return i\n",
    "        print(col[:m + 1])\n",
    "        print(row[:m + 1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        in_deg = [0] * 1000\n",
    "        out_deg = [0] * 1000\n",
    "        max_idx = 0\n",
    "\n",
    "        for edge in path:\n",
    "            in_deg[edge[1]] += 1\n",
    "            out_deg[edge[0]] += 1\n",
    "\n",
    "            max_idx_temp = max(edge)\n",
    "            if max_idx_temp > max_idx:\n",
    "                max_idx = max_idx_temp\n",
    "\n",
    "        for idx in range(max_idx + 1):\n",
    "            if out_deg[idx] == 0 and in_deg[idx] == max_idx:\n",
    "                return idx\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        nodes = set()\n",
    "        out_deg = Counter()\n",
    "        in_deg = Counter()\n",
    "        for x, y in path:\n",
    "            nodes.add(x)\n",
    "            nodes.add(y)\n",
    "            out_deg[x] += 1\n",
    "            in_deg[y] += 1\n",
    "        for x in nodes:\n",
    "            if out_deg[x] == 0 and in_deg[x] == len(nodes) - 1:\n",
    "                return x\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        start = {}\n",
    "        end = {}\n",
    "        nodes = set()\n",
    "        for a, b in path:\n",
    "            if a not in start:\n",
    "                start[a] = 0\n",
    "            if b not in end:\n",
    "                end[b] = 0\n",
    "            start[a] += 1\n",
    "            end[b] += 1\n",
    "            nodes.add(a)\n",
    "            nodes.add(b)\n",
    "        for n in nodes:\n",
    "            if n in end and n not in start and end[n] == len(nodes)-1:\n",
    "                return n\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        area: set = set()\n",
    "        arrival = defaultdict(int)\n",
    "        for i in range(len(path)):\n",
    "            area.add(path[i][0])\n",
    "            area.add(path[i][1])\n",
    "        num_area = len(area)\n",
    "        for i in range(len(path)):\n",
    "            area.discard(path[i][0])\n",
    "            arrival[path[i][1]] += 1\n",
    "\n",
    "        if not area:\n",
    "            return -1\n",
    "        a = area.pop()\n",
    "        if arrival[a] == num_area - 1:\n",
    "            return a\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        n = 0\n",
    "        for p in path:\n",
    "            n = max(n, max(p) + 1)\n",
    "            \n",
    "        g = [[] for _ in range(n)]\n",
    "        indegs, outdegs = [0] * n, [0] * n\n",
    "        for x, y in path:\n",
    "            indegs[y] += 1\n",
    "            outdegs[x] += 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            if indegs[i] == n - 1 and outdegs[i] == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        max_n = 0\n",
    "        for p in path:\n",
    "            max_n = max(max(p[0], p[1]), max_n)\n",
    "        max_n += 1\n",
    "        out_dim = [[] for _ in range(max_n)]\n",
    "        in_dim = [[] for _ in range(max_n)]\n",
    "        for p in path:\n",
    "            out_dim[p[0]].append(p[1])\n",
    "            in_dim[p[1]].append(p[0])\n",
    "        for i in range(max_n):\n",
    "            if len(out_dim[i]) == 0 and len(in_dim[i]) == max_n - 1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        dic = {}\n",
    "        for edge in path:\n",
    "            if edge[0] not in dic:\n",
    "                dic[edge[0]] = [1, 0]\n",
    "            elif edge[0] in dic:\n",
    "                dic[edge[0]][0] += 1\n",
    "            if edge[1] not in dic:\n",
    "                dic[edge[1]] = [0, 1]\n",
    "            elif edge[1] in dic:\n",
    "                dic[edge[1]][1] += 1\n",
    "        for key in dic.keys():\n",
    "            if dic[key][0] == 0 and dic[key][1] == len(dic) - 1:\n",
    "                return key\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "\n",
    "        station = set()\n",
    "        for a, b in path:\n",
    "            if a not in station:\n",
    "                station.add(a)\n",
    "            if b not in station:\n",
    "                station.add(b)\n",
    "        n = len(station)\n",
    "\n",
    "        for i in station:\n",
    "            ln = 0\n",
    "            for a, b in path:\n",
    "                if a == i:\n",
    "                    break\n",
    "\n",
    "                if b == i:\n",
    "                    ln += 1\n",
    "            if ln == n - 1:\n",
    "                return i \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        nodes = set()\n",
    "        out_deg = defaultdict(int)\n",
    "        in_deg = defaultdict(int)\n",
    "        for x, y in path:\n",
    "            nodes.add(x)\n",
    "            nodes.add(y)\n",
    "            out_deg[x] += 1\n",
    "            in_deg[y] += 1\n",
    "        for x in nodes:\n",
    "            if out_deg[x] == 0 and in_deg[x] == len(nodes) - 1:\n",
    "                return x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        n = len(path)\n",
    "        max_p = -1\n",
    "        for p in path:\n",
    "            max_p = max(max_p, max(p))\n",
    "\n",
    "        s = [0] * (max_p+1)\n",
    "        for p in path:\n",
    "            s[p[1]] += 1\n",
    "            s[p[0]] -= 1\n",
    "        for i, num in enumerate(s):\n",
    "            if num == max_p:\n",
    "                return i\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        nodes = set()\n",
    "        out_deg = Counter()\n",
    "        in_deg = Counter()\n",
    "        for x, y in path:\n",
    "            nodes.add(x)\n",
    "            nodes.add(y)\n",
    "            out_deg[x] += 1\n",
    "            in_deg[y] += 1\n",
    "        for x in nodes:\n",
    "            if out_deg[x] == 0 and in_deg[x] == len(nodes) - 1:\n",
    "                return x\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        nodes = set()\n",
    "        outs = defaultdict(int)\n",
    "        ins = defaultdict(int)\n",
    "\n",
    "        for ele in path:\n",
    "            nodes.add(ele[0])\n",
    "            nodes.add(ele[1])\n",
    "\n",
    "            outs[ele[0]] += 1\n",
    "            ins[ele[1]] += 1\n",
    "\n",
    "        for node in nodes:\n",
    "            if outs[node] == 0 and ins[node] == len(nodes) - 1:\n",
    "                return node\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        nodes = set()\n",
    "        out_deg = Counter()\n",
    "        in_deg = Counter()\n",
    "        for x, y in path:\n",
    "            nodes.add(x)\n",
    "            nodes.add(y)\n",
    "            out_deg[x] += 1\n",
    "            in_deg[y] += 1\n",
    "        for x in nodes:\n",
    "            if out_deg[x] == 0 and in_deg[x] == len(nodes) - 1:\n",
    "                return x\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        outdegree= {}\n",
    "        indegree= {}\n",
    "        s=set()\n",
    "        for a, b in path:\n",
    "            s.add(a)\n",
    "            s.add(b)\n",
    "            if a in outdegree:\n",
    "                outdegree[a]+=1\n",
    "            else:\n",
    "                outdegree[a]=1\n",
    "            if b in indegree:\n",
    "                indegree[b]+=1\n",
    "            else:\n",
    "                indegree[b]=1\n",
    "        n=len(s)\n",
    "        print(outdegree.items())\n",
    "        print(indegree.items())\n",
    "        for key, val in indegree.items():\n",
    "            if val==n-1:\n",
    "                if key not in outdegree:\n",
    "                    return key\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        node = set()\n",
    "        flag = set()\n",
    "        cnt = 0\n",
    "        tag = {}\n",
    "        for i, j in path:\n",
    "            if j not in tag:\n",
    "                tag[j] = [set(), 0]\n",
    "            tag[j][0].add(i)\n",
    "            tag[j][1] += 1\n",
    "            if j not in node:\n",
    "                node.add(j)\n",
    "                cnt += 1\n",
    "            if i not in node:\n",
    "                node.add(i)\n",
    "                cnt += 1\n",
    "            flag.add(i)\n",
    "        for i in tag:\n",
    "            if tag[i][1] == cnt - 1 and i not in flag:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        #指向的哈希表\n",
    "        #get cities\n",
    "        cities = []\n",
    "        for i in path:\n",
    "            for j in i:\n",
    "                if j not in cities:\n",
    "                   cities.append(j) \n",
    "        n = len(cities)\n",
    "        pointed = collections.defaultdict(list)\n",
    "        for p in path:\n",
    "            pointed[p[1]].append(p[0])\n",
    "        value = []\n",
    "        c = -1\n",
    "        for k,v in pointed.items():\n",
    "            if len(v)==n-1:\n",
    "                value = v\n",
    "                c = k\n",
    "                break\n",
    "        if c == -1:\n",
    "            return -1\n",
    "        else:\n",
    "            for v in pointed.values():\n",
    "                if c in v:\n",
    "                    return -1\n",
    "            return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        degre = {}\n",
    "        for pt in path:\n",
    "            if pt[0] in degre:\n",
    "                degre[pt[0]][0] += 1\n",
    "            else:\n",
    "                degre[pt[0]] = [1, 0]\n",
    "            \n",
    "            if pt[1] in degre:\n",
    "                degre[pt[1]][1] += 1\n",
    "            else:\n",
    "                degre[pt[1]] = [0, 1]\n",
    "        \n",
    "        nodesnum = len(degre)\n",
    "        ans = -1\n",
    "        for key in degre:\n",
    "            if (degre[key][0] == 0) and (degre[key][1] == (nodesnum - 1)):\n",
    "                ans = key\n",
    "                break\n",
    " \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "\n",
    "        station = set()\n",
    "        for a, b in path:\n",
    "            if a not in station:\n",
    "                station.add(a)\n",
    "            if b not in station:\n",
    "                station.add(b)\n",
    "        n = len(station)\n",
    "\n",
    "        for i in station:\n",
    "            ln = 0\n",
    "            for a, b in path:\n",
    "                if a == i:\n",
    "                    break\n",
    "\n",
    "                if b == i:\n",
    "                    ln += 1\n",
    "            if ln == n - 1:\n",
    "                return i \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        start = [x[0] for x in path]\n",
    "        stop = [x[1] for x in path]\n",
    "        tmp = list(set(stop).difference(set(start)))\n",
    "        node = list(set(start + stop))\n",
    "        if not tmp:\n",
    "            return -1\n",
    "        path_dict = collections.defaultdict(list)\n",
    "        for s, e in path:\n",
    "            if e in tmp:\n",
    "                path_dict[e].append(s)\n",
    "        for n in tmp:\n",
    "            if len(path_dict[n]) == len(node)-1:\n",
    "                return n\n",
    "        return -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        in_map = defaultdict(int)\n",
    "        out_map = defaultdict(int)\n",
    "        ins = set()\n",
    "        for a, b in path:\n",
    "            in_map[b] += 1\n",
    "            out_map[a] += 1 \n",
    "            ins.add(b)\n",
    "            ins.add(a)\n",
    "        for k, v in in_map.items():\n",
    "            if v == len(ins) - 1:\n",
    "                if k not in out_map:\n",
    "                    return k\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        in_, out_ = Counter(), Counter()\n",
    "        st = set()\n",
    "        for a, b in path:\n",
    "            out_[a] += 1\n",
    "            in_[b] += 1\n",
    "            st.add(a)\n",
    "            st.add(b)\n",
    "\n",
    "        for x in st:\n",
    "            if in_[x] == len(st) - 1 and out_[x] == 0:\n",
    "                return x\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        start = [x[0] for x in path]\n",
    "        stop = [x[1] for x in path]\n",
    "        tmp = list(set(stop).difference(set(start)))\n",
    "        node = list(set(start + stop))\n",
    "        if not tmp:\n",
    "            return -1\n",
    "        path_dict = collections.defaultdict(int)\n",
    "        for s, e in path:\n",
    "            if e in tmp:\n",
    "                path_dict[e] += 1\n",
    "        for n in tmp:\n",
    "            if path_dict[n] == len(node)-1:\n",
    "                return n\n",
    "        return -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        arrival: Dict[int, List] = defaultdict(list)\n",
    "        start: set = set()\n",
    "        lines: set = set()\n",
    "        for i in range(len(path)):\n",
    "            arrival[path[i][1]].append(path[i][0])\n",
    "            start.add(path[i][0])\n",
    "            lines.add(path[i][0])\n",
    "            lines.add(path[i][1])\n",
    "        for k, v in arrival.items():\n",
    "            if len(v) == len(lines) - 1 and k not in start:\n",
    "                return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        nodes = set()\n",
    "        out_deg = Counter()\n",
    "        in_deg = Counter()\n",
    "        for x, y in path:\n",
    "            nodes.add(x)\n",
    "            nodes.add(y)\n",
    "            out_deg[x] += 1\n",
    "            in_deg[y] += 1\n",
    "        for x in nodes:\n",
    "            if out_deg[x] == 0 and in_deg[x] == len(nodes) - 1:\n",
    "                return x\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        m = defaultdict(int)\n",
    "        \n",
    "        # 入度\n",
    "        for p in path:\n",
    "            m[p[1]] += 1\n",
    "        \n",
    "        # 出度\n",
    "        for p in path:\n",
    "            m[p[0]] -= 1\n",
    "        \n",
    "        ans = -1\n",
    "        n = len(m)\n",
    "        \n",
    "        for f, s in m.items():\n",
    "            if s == (n - 1):\n",
    "                ans = f\n",
    "                break\n",
    "                \n",
    "        return ans\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "print(sol.transportationHub([[1, 2], [2, 3], [3, 1], [3, 4]]))  # 输出应该为 3\n",
    "print(sol.transportationHub([[1, 2], [2, 3], [3, 1]]))  # 输出应该为 -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        n = len(path)\n",
    "        in_map = defaultdict(int)\n",
    "        out_map = defaultdict(int)\n",
    "        ins = set()\n",
    "        for a, b in path:\n",
    "            in_map[b] += 1\n",
    "            out_map[a] += 1 \n",
    "            ins.add(b)\n",
    "            ins.add(a)\n",
    "        for k, v in in_map.items():\n",
    "            if v == len(ins) - 1:\n",
    "                if k not in out_map:\n",
    "                    return k\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        res = -1\n",
    "        node_set = set()\n",
    "        g = defaultdict(list)\n",
    "        ind = defaultdict(int)\n",
    "        outd = defaultdict(int)\n",
    "        for a,b in path:\n",
    "            g[a].append(b)\n",
    "            ind[b]+=1\n",
    "            outd[a]+=1\n",
    "            node_set.add(a)\n",
    "            node_set.add(b)\n",
    "        \n",
    "        n = len(node_set)\n",
    "        for node in node_set:\n",
    "            if ind[node] == n-1 and outd[node] == 0:\n",
    "                res = node\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        nodes = set()\n",
    "        source, dst = Counter(), Counter()\n",
    "        for i, j in path:\n",
    "            nodes.add(i)\n",
    "            nodes.add(j)\n",
    "            source[i] += 1\n",
    "            dst[j] += 1\n",
    "        n = len(nodes)\n",
    "        for node in nodes:\n",
    "            if source[node] == 0 and dst[node] == n - 1:\n",
    "                return node\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        start = [x[0] for x in path]\n",
    "        stop = [x[1] for x in path]\n",
    "        tmp = list(set(stop).difference(set(start)))\n",
    "        node = list(set(start + stop))\n",
    "        if not tmp:\n",
    "            return -1\n",
    "        path_dict = collections.defaultdict(int)\n",
    "        for s, e in path:\n",
    "            path_dict[e] += 1\n",
    "        for n in tmp:\n",
    "            if path_dict[n] == len(node)-1:\n",
    "                return n\n",
    "        return -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        n = len(path)\n",
    "        in_map = defaultdict(int)\n",
    "        out_map = defaultdict(int)\n",
    "        ins = set()\n",
    "        for i in range(n):\n",
    "            out_map[i] = 0\n",
    "        for a, b in path:\n",
    "            in_map[b] += 1\n",
    "            out_map[a] += 1 \n",
    "            ins.add(b)\n",
    "            ins.add(a)\n",
    "        for k, v in in_map.items():\n",
    "            if v == len(ins) - 1:\n",
    "                if k not in out_map or out_map[k] == 0:\n",
    "                    return k\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        eleset = set()\n",
    "        elecount = defaultdict(int)\n",
    "        for i in range(len(path)):\n",
    "            eleset.add(path[i][0])\n",
    "            eleset.add(path[i][1])\n",
    "            w1 , w2 = (path[i][0],0) ,(path[i][1],1)\n",
    "            elecount[w1] += 1\n",
    "            elecount[w2] += 1\n",
    "            pass\n",
    "\n",
    "        for ele in eleset:\n",
    "            if elecount[(ele,0)] == 0 and elecount[(ele,1)] == len(eleset)-1:\n",
    "                return ele\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        s = set()\n",
    "        indeg = {}\n",
    "        outdeg = {}\n",
    "        for i, j in path:\n",
    "            s.add(i)\n",
    "            s.add(j)\n",
    "            indeg[j] = indeg.get(j, 0) + 1\n",
    "            outdeg[i] = outdeg.get(i, 0) + 1\n",
    "        n = len(s)\n",
    "        for i in s:\n",
    "            if i not in outdeg and indeg.get(i, 0) == n - 1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        start = [x[0] for x in path]\n",
    "        stop = [x[1] for x in path]\n",
    "        tmp = list(set(stop).difference(set(start)))\n",
    "        node = list(set(start + stop))\n",
    "        if not tmp:\n",
    "            return -1\n",
    "        path_dict = collections.defaultdict(list)\n",
    "        for s, e in path:\n",
    "            path_dict[e].append(s)\n",
    "        for n in tmp:\n",
    "            if len(path_dict[n]) == len(node)-1:\n",
    "                return n\n",
    "        return -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        end = defaultdict(int)\n",
    "        start = defaultdict(int)\n",
    "        for s, e in path:\n",
    "            end[e] += 1\n",
    "            start[s] += 1\n",
    "        n = len(set(start.keys()) | set(end.keys()))\n",
    "        for i in end:\n",
    "            if ((end[i]) == n - 1) and (i not in start):\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        ans = set()\n",
    "        out_map = defaultdict(int)\n",
    "        in_map = defaultdict(int)\n",
    "        for i, j in path:\n",
    "            ans.add(i)\n",
    "            ans.add(j)\n",
    "            in_map[j] += 1\n",
    "            out_map[i] += 1\n",
    "        n = len(ans)\n",
    "        for i in range(n):\n",
    "            if out_map[i] == 0 and in_map[i] == n - 1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        nums,dic = set(),defaultdict(set)\n",
    "        for f,t in path:\n",
    "            nums.add(f)\n",
    "            nums.add(t)\n",
    "            dic[f].add(t)\n",
    "        queue = deque([i for i in nums if i not in dic])\n",
    "        N = len(nums) - 1\n",
    "        #print(queue,dic,N)\n",
    "        while queue:\n",
    "            t = queue.popleft()\n",
    "            n = N\n",
    "            for key,values in dic.items():\n",
    "                if t in values:\n",
    "                    n -= 1\n",
    "            if n == 0:\n",
    "                return t\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        path_dict = defaultdict(set)\n",
    "        source_node, dst_node = set(), set()\n",
    "        for i, j in path:\n",
    "            path_dict[j].add(i)\n",
    "            source_node.add(i)\n",
    "            dst_node.add(j)\n",
    "        n = len(source_node | dst_node)\n",
    "        new = dst_node - source_node\n",
    "        for node in new:\n",
    "            if node in path_dict and len(path_dict[node]) == n - 1:\n",
    "                return node\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        path1 = []\n",
    "        an_path = []\n",
    "        res = []\n",
    "        all_nu = []\n",
    "        n = len(path)\n",
    "        for i in range(n):\n",
    "            path1.append(path[i][0])\n",
    "            an_path.append(path[i][1])\n",
    "            all_nu.append(path[i][0])\n",
    "            all_nu.append(path[i][1])\n",
    "        all_nu = set(all_nu)\n",
    "        for j in range(n):\n",
    "            if path[j][1] not in path1:\n",
    "                res.append(path[j][1])\n",
    "        for k in res:\n",
    "            tem = []\n",
    "            for v in range(n):\n",
    "                if path[v][1] == k:\n",
    "                    tem.append(path[v][0])\n",
    "            tem = set(tem)\n",
    "            if tem == all_nu - {k}:\n",
    "                return k\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        tu1 = collections.defaultdict(list)\n",
    "        tu2 = collections.defaultdict(list)\n",
    "        tu3 = collections.defaultdict(int)\n",
    "        for i in path:\n",
    "            tu1[i[0]].append(i[1])\n",
    "            tu2[i[1]].append(i[0])\n",
    "            tu3[i[1]] += 1\n",
    "            tu3[i[0]] += 1\n",
    "\n",
    "        nums = len(tu3.keys())\n",
    "        for i in tu2:\n",
    "            if len(tu2[i]) == nums-1 and len(tu1[i]) == 0:\n",
    "                return i \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        trace = {}\n",
    "        points = []\n",
    "        for p in path:\n",
    "            a, b = p[0], p[1]\n",
    "            points.append(a)\n",
    "            points.append(b)\n",
    "            if not a in trace:\n",
    "                trace[a] = [0, 0]\n",
    "            if not b in trace:\n",
    "                trace[b] = [0, 0]\n",
    "            at, bt = trace[a], trace[b]\n",
    "            trace[a] = [at[0] + 1, at[1]]\n",
    "            trace[b] = [bt[0], bt[1] + 1]\n",
    "        n = len(set(points))\n",
    "        # print(n)\n",
    "        for k in trace:\n",
    "            if trace[k][0] == 0 and trace[k][1] == n - 1:\n",
    "                return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        set_start, set_all = set(), set()\n",
    "        for list_path in path:\n",
    "            set_start.add(list_path[0])\n",
    "            set_all.add(list_path[0])\n",
    "            set_all.add(list_path[1])\n",
    "        if len(set_start) == len(set_all):\n",
    "            # 所有节点都是起始点\n",
    "            return -1\n",
    "        else:\n",
    "            list_nomet_condition1 = []\n",
    "            set_no_start = set_all-set_start\n",
    "            set_no_start_copy = set_no_start.copy()\n",
    "            # 拿到了所有非起始点\n",
    "            for i in iter(set_no_start):\n",
    "                set_no_self = set(set_all) - {i}\n",
    "                for j in iter(set_no_self):\n",
    "                    if [j,i] not in path:\n",
    "                        # 筛选出所有不满足条件1的节点\n",
    "                        set_no_start_copy.discard(i)\n",
    "            if len(set_no_start_copy)==1:\n",
    "                return list(set_no_start_copy)[0]\n",
    "            elif len(set_no_start_copy)==0:\n",
    "                return -1\n",
    "            else:\n",
    "                return None\n",
    "\n",
    "                        \n",
    "                \n",
    "\n",
    "                       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transportationHub(self, path: List[List[int]]) -> int:\n",
    "        path1 = []\n",
    "        an_path = []\n",
    "        res = []\n",
    "        all_nu = []\n",
    "        n = len(path)\n",
    "        for i in range(n):\n",
    "            path1.append(path[i][0])\n",
    "            an_path.append(path[i][1])\n",
    "            all_nu.append(path[i][0])\n",
    "            all_nu.append(path[i][1])\n",
    "        all_nu = set(all_nu)\n",
    "        for j in range(n):\n",
    "            if path[j][1] not in path1:\n",
    "                res.append(path[j][1])\n",
    "        res = list(set(res))\n",
    "        for k in res:\n",
    "            tem = []\n",
    "            for v in range(n):\n",
    "                if path[v][1] == k:\n",
    "                    tem.append(path[v][0])\n",
    "            tem = set(tem)\n",
    "            if tem == all_nu - {k}:\n",
    "                return k\n",
    "        return -1\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
